package com.chj.zhongji.class13;

//https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/javashi-xian-shen-du-you-xian-chao-ji-jian-dan-yi-/
public class Code02_LongestIncreasingPath {

	public static int maxPath(int[][] matrix) {
		int ans = Integer.MIN_VALUE;
		for (int row = 0; row < matrix.length; row++) {
			for (int col = 0; col < matrix[0].length; col++) {
				ans = Math.max(ans, process(matrix, row, col));
			}
		}
		return ans;
	}

	// 假设在matrix中，从i行，j列出发，能走出的最长递增路径，返回
	public static int process(int[][] matrix, int i, int j) {
		if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
			return -1;
		}
		int next1 = 0;
		int next2 = 0;
		int next3 = 0;
		int next4 = 0;
		if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
			next1 = process(matrix, i - 1, j);
		}
		if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
			next2 = process(matrix, i + 1, j);
		}
		if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
			next3 = process(matrix, i, j - 1);
		}
		if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
			next4 = process(matrix, i - 1, j);
		}
		return 1 + Math.max(Math.max(next1, next2), Math.max(next3, next4));
	}

	public static int maxPath2(int[][] matrix) {
		int ans = Integer.MIN_VALUE;

		int[][] dp = new int[matrix.length][matrix[0].length];

		for (int row = 0; row < matrix.length; row++) {
			for (int col = 0; col < matrix[0].length; col++) {
				ans = Math.max(ans, process(matrix, row, col, dp));
			}
		}
		return ans;
	}

	// 假设在matrix中，从i行，j列出发，能走出的最长递增路径，返回
	public static int process(int[][] matrix, int i, int j, int[][] dp) {
		if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
			return -1;
		}
		if (dp[i][j] != 0) {
			return dp[i][j];
		}
		int next1 = 0;
		int next2 = 0;
		int next3 = 0;
		int next4 = 0;
		if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
			next1 = process(matrix, i - 1, j);
		}
		if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
			next2 = process(matrix, i + 1, j);
		}
		if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
			next3 = process(matrix, i, j - 1);
		}
		if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
			next4 = process(matrix, i - 1, j);
		}

		int ans = 1 + Math.max(Math.max(next1, next2), Math.max(next3, next4));
		dp[i][j] = ans;
		return ans;
	}

	public static int longestIncreasingPath(int[][] m) {
		if (m == null || m.length == 0 || m[0].length == 0) {
			return 0;
		}
		int[][] dp = new int[m.length][m[0].length];
		// dp[i][j] (i,j)出发，走出的最长链长度
		int max = 0;
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[0].length; j++) {
				// 每一个(i,j)位置出发，都尝试
				max = Math.max(max, maxIncrease(m, dp, i + 1, j, m[i][j]) + 1);
				max = Math.max(max, maxIncrease(m, dp, i, j + 1, m[i][j]) + 1);
				max = Math.max(max, maxIncrease(m, dp, i - 1, j, m[i][j]) + 1);
				max = Math.max(max, maxIncrease(m, dp, i, j - 1, m[i][j]) + 1);
			}

		}
		return max;
	}

	// 来到的当前位置是i,j位置
	// p 上一步值是什么
	// 从(i,j)位置出发，走出的最长链，要求：上一步是可以迈到当前步上的
	public static int maxIncrease(int[][] m, int[][] dp, int i, int j, int p) {
		if (i < 0 || i >= m.length || j < 0 || j >= m[0].length || m[i][j] <= p) {
			return 0;
		}
		if (dp[i][j] == 0) { // i,j 出发，当前没算过
			dp[i][j] = maxIncrease(m, dp, i + 1, j, m[i][j]) + 1;
			dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i, j + 1, m[i][j]) + 1);
			dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i - 1, j, m[i][j]) + 1);
			dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i, j - 1, m[i][j]) + 1);
		}
		return dp[i][j];
	}

	public static int longestIncreasingPath2(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}
		// visited有两个作用：1.判断是否访问过，2.存储当前格子的最长递增长度
		int[][] visited = new int[matrix.length][matrix[0].length];
		int max = 0;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (visited[i][j] == 0) {
					// 这里先做一次比较找出max，可以避免最后再去遍历一个visited数组
					max = Math.max(max, dfs(i, j, matrix, visited));
				}
				// max = Math.max(max, visited[i][j]);

			}
		}
		return max;
	}

	public static int dfs(int i, int j, int[][] matrix, int[][] visited) {
		if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
			return 0;
		}
		if (visited[i][j] > 0) {
			return visited[i][j];
		}
		int max = 0;
		// 这里分别去判断4周是否比当前数小，然后去递归遍历
		if (i - 1 >= 0 && matrix[i - 1][j] < matrix[i][j]) {
			max = Math.max(max, dfs(i - 1, j, matrix, visited));
		}
		if (i + 1 < matrix.length && matrix[i + 1][j] < matrix[i][j]) {
			max = Math.max(max, dfs(i + 1, j, matrix, visited));
		}
		if (j - 1 >= 0 && matrix[i][j - 1] < matrix[i][j]) {
			max = Math.max(max, dfs(i, j - 1, matrix, visited));
		}
		if (j + 1 < matrix[0].length && matrix[i][j + 1] < matrix[i][j]) {
			max = Math.max(max, dfs(i, j + 1, matrix, visited));
		}

		visited[i][j] = max + 1;
		return max + 1;

	}

	public static void main(String[] args) {
		{
//			输出: 4 
//			解释: 最长递增路径为 [1, 2, 6, 9]
			int[][] matrix = new int[][] { { 9, 9, 4 }, { 6, 6, 8 }, { 2, 1, 1 } };
			System.err.println(longestIncreasingPath2(matrix));
			System.err.println(longestIncreasingPath(matrix));
			System.out.println(maxPath(matrix));
		}
		System.out.println();
		{
//			输出: 4 
//			解释: 最长递增路径为 [1, 2, 6, 9]
			int[][] matrix = new int[][] { { 3, 4, 5 }, { 3, 2, 6 }, { 2, 2, 1 } };
			System.err.println(longestIncreasingPath2(matrix));
			System.err.println(longestIncreasingPath(matrix));
			System.out.println(maxPath(matrix));
		}
		System.out.println();
		{
			int[][] matrix2 = new int[][] { { 5, 4, 3 }, { 3, 1, 2 }, { 2, 1, 3 } };
			System.err.println(longestIncreasingPath2(matrix2));
			System.err.println(longestIncreasingPath(matrix2));
			System.out.println(maxPath(matrix2));
		}
	}
}
